package code;

public class Code43 {
	/*
	 * 两个大数相×
	 */
	
    public String multiply(String num1, String num2) {
    	
    	int n=num1.length();
    	int m=num2.length();
    	
    	if(num1.equals("0") || num2.equals("0"))
    		return "0";
    	int[] A=new int[n];
    	int[] B=new int[m];
    	int i,j;
    	for(i=0;i<n;i++){
    		A[i]=num1.charAt(n-i-1)-'0';
    	}
    	for(i=0;i<m;i++){
    		B[i]=num2.charAt(m-i-1)-'0';
    	}
    	int[] C=new int[n+m];
    	
    	for(i=0;i<n;i++){
    		/*
    		 * A的第i位与B[]相×
    		 */
    		int add=0;
    		for(j=0;j<m;j++){
    			int x=A[i]*B[j]+add;
    			if(x>9){
    				add=x/10;
    				x%=10;
    			}
    			else add=0;
    			C[i+j]+=x;
    		}
    		if(add>0){
    			C[i+m]+=add;
    			add=0;
    		}
        	/*
        	 * C[]有可能会有>=10的数
        	 */
    		add=0;
        	for(j=0;j<n+m;j++){
        		C[j]+=add;
        		if(C[j]>9){
        			C[j]-=10;
        			add=1;
        		}
        		else add=0;
        	}
    	}
    	StringBuilder sb=new StringBuilder();
    	/*
    	 * 去掉前导0
    	 */
    	for(i=m+n-1;C[i]==0 && i>=0;i--)
    		;
    	for(;i>=0;i--){
    		sb.append(C[i]);
    	}
        return sb.toString();
    }
    public static void main(String[] args){
    	String a="999";
    	String b="999";
    	System.out.println(new Code43().multiply(a, b));
    }
}
